Ogni volta che una variabile compare in una formula diremo che è un’occorrenza della variabile nella formula. In ogni formula occorrono un numero finito di variabili.
La variabile \(z\) occorre tre volte in \[((\exists x \left ( f(x,y) = c \right )) \to ( (\forall z (R ( z ))) \vee (S ( z )) )) .\] Nelle prime due occorrenze la \(z\) è muta dato che dire \((\forall z (R ( z )))\) ha lo stesso significato di \((\forall u (R ( u )))\), cioè ogni oggetto gode della proprietà \(R\), mentre la terza occorrenza serve per asserire che \(z\) gode della proprietà \(S\).
Le occorrenze del primo tipo si dicono vincolate, quelle del secondo tipo si dicono libere.
La distinzione tra occorrenze libere e vincolate di una variabile è importante perché tali occorrenze verranno trattate in maniera diversa quando parleremo di semantica (ovvero di interpretazione di formule).
Perché distinguere tra variabili libere e vincolate? Consideriamo il linguaggio \(L=\{+,\cdot,0,1\}\) con \(+,\cdot\) simboli di operazione binari e \(0,1\) simboli di costante.
L’equazione \(x^2+2x=0\) può essere espressa in questo linguaggio dalla formula atomica \(\phi(x)\) \[(+( \cdot(x,x), +(x,x))=0).\]
La formula \(\psi\) \[(\exists x\,(+( \cdot(x,x), +(x,x))=0))\] esprime invece l’asserzione
“Esiste \(x\) tale che \(x^2+2x=0\)”
ovvero: “L’equazione \(x^2 + 2x = 0\) ammette una soluzione”.
Si osservi che tutte le occorrenze di \(x\) in \(\phi(x)\) sono libere, mentre \(\psi\) è un enunciato (ovvero non ha variabili libere).
Supponiamo ora di interpretare tutti i simboli \(+ , \cdot , 0, 1\) di \(L\) nella maniera usuale, e di voler stabilire se \(\phi(x)\) e \(\psi\) sono vere in \(\mathbb{R}\).
L’espressione \(\phi(x)\), che rappresenta l’equazione \(x^2 + 2x = 0\), non è né vera né falsa in \(\mathbb{R}\)! Tutto dipende da che valore assegniamo alla variabile (libera!) \(x\): se a \(x\) assegniamo il valore \(5\), allora otteniamo un’affermazione falsa (cioè \(5^2 + 2 \cdot 5 = 0\)); se a \(x\) assegniamo il valore \(0\) oppure il valore \(-2\), l’affermazione sarà invece vera.
L’espressione \(\psi\), che corrisponde a “l’equazione \(x^2 + 2x = 0\) ammette soluzioni”, è invece vera in \(\mathbb{R}\), non c’è alcun bisogno di assegnare valori alle variabili per decidere se sia vera o meno (tutte le variabili sono vincolate!).
Le variabili libere di una formula sono quelle a cui dobbiamo assegnare un valore per poter stabilire se la formula è vera oppure no in un dato contesto!
Variabili libere e vincolate
Sia \(\phi\) una formula e \(x\) una variabile.
Se \(\phi\) è atomica allora ogni occorrenza di \(x\) in \(\phi\) è libera.
Se \(\phi\) è della forma \((\neg \psi)\) allora le occorrenze libere di \(x\) in \(\phi\) sono esattamente quelle di \(x\) in \(\psi\).
Se \(\phi\) è della forma \(( \psi \mathrel{\Box} \chi )\), dove \(\Box\) è un connettivo binario, allora le occorrenze libere di \(x\) in \(\phi\) sono quelle di \(x\) in \(\psi\) e quelle di \(x\) in \(\chi\).
Se \(\phi\) è della forma \((\exists y \, \psi)\) oppure \((\forall y \, \psi)\) con \(y\) una variabile diversa da \(x\), allora le occorrenze libere di \(x\) in \(\phi\) sono esattamente le sue occorrenze libere in \(\psi\).
Se \(\phi\) è della forma \((\exists x \, \psi)\) oppure \((\forall x \, \psi)\), allora tutte le occorrenze di \(x\) in \(\phi\) sono vincolate.
Più brevemente: un’occorrenza di una variabile \(x\) in \(\phi\) è vincolata se segue un quantificatore, oppure cade nel raggio d’azione di un quantificatore del tipo \(\exists x\) o \(\forall x\). In caso contrario, l’occorrenza in questione si dice libera.
Definizione Si dice che \(x\) occorre libera in \(\phi\) (oppure che \(x\) è una variabile libera di \(\phi\)) se c’è almeno un’occorrenza libera di \(x\) in \(\phi\). L’insieme delle variabili libere di \(\phi\) è indicato con \[FV (\phi).\]
La notazione
\(\phi ( x_{1} , \dots , x_{n} )\)
serve per porre in evidenza il fatto che le variabili che occorrono libere in \(\phi\) sono alcune tra le \(x_{1} , \dots , x_{n}\).
Attenzione! Non richiediamo che ogni \(x_{1} , \dots , x_{n}\) compaia libera (o compaia del tutto) in \(\phi\) ed è perfettamente possibile che la formula non contenga alcuna variabile libera, o addirittura nessuna variabile: stiamo solo dicendo che se c’è una variabile che occorre libera in \(\phi\), allora è una tra le \(x_{1}, \dotsc, x_{n}\).
Definizione: Un enunciato o formula chiusa è una formula che non contiene variabili libere, cioè tale che \(FV ( \phi ) = \emptyset\).
Per comodità, quando vogliamo specificare il linguaggio \(L\) in cui l’enunciato è formulato parliamo di \(L\)-enunciato.
Per individuare le (eventuali) occorrenze libere di una variabile \(x\) in una data formula \(\phi\), si può analizzare l’albero sintattico nel seguente modo.
Si calcola l’albero sintattico di \(\phi\).
Se l’occorrenza di \(x\) cui siamo interessati segue un quantificatore, allora tale occorrenza è vincolata.
In caso contrario, si individua l’unico ramo dell’albero sintattico che mostra da dove proviene l’occorrenza in questione (si veda l’esempio seguente).
Se lungo tale ramo viene “applicata” una quantificazione proprio sulla variabile \(x\), allora l’occorrenza di \(x\) in questione è vincolata (in quanto cade nel raggio d’azione di quel quantificatore).
Se invece lungo tutto il ramo non si quantifica mai su \(x\), allora l’occorrenza di \(x\) in questione è libera.
Consideriamoesempio_par la formula \[((\exists x (\forall y \left ( (P ( x , y )) \to (Q ( x )) \right ) ) )\to ((\forall z (R ( z ))) \vee (S ( z ))))\] Il suo albero sintattico è
L’albero sintattico di \[((\exists x (\forall y ( (P ( x , y )) \to (Q ( x )) ) ) )\to ((\forall z (R ( z ))) \vee (S ( z ))))\] è
Osservazioni:
Se un’occorrenza di una variabile segue un quantificatore, allora è certamente un’occorrenza vincolata.
Data un’occorrenza di variabile che non segua un quantificatore, si considera innanzituttutto il cammino lungo l’albero sintattico da cui proviene.
Nella foglia, l’occorrenza della variabile è certamente libera perché in una formula atomica non ci sono quantificatori.
Risalendo il ramo, la variabile continua a restare libera finché non viene introdotto un quantificatore.
Quando si arriva ad un nodo in cui si introduce un nuovo quantifica- tore, si controlla se è una quantificazione sulla variabile in questione o su una variabile diversa.
Nel secondo caso (quantificazione su variabile diversa), la variabile resta libera.
Se la quantificazione è su quella variabile, allora l’occorrenza diventa vincolata e resta vincolata fino al termine del ramo (cioè è un’occorrenza vincolata nella formula che stiamo analizzando).
Si procede poi analizzando ogni occorrenza di variabile. L’occorrenza è vincolata se lungo il cammino corrispondente viene vincolata da un quantificatore sulla variabile in questione, se ciò non accade, l'occorrenza sarà libera.
Quest’analisi permette di individuare in maniera algoritmica le occorrenze libere e vincolate delle variabili nella formula in questione.
Sia \(L = \{ P, Q, f, a, c \}\) un linguaggio del prim’ordine dove \(P\) è un simbolo di predicato binario, \(Q\) è un simbolo di predicato unario, \(f\) è un simbolo di funzione unario e \(a , c\) sono simboli di costante. Per ciascuna occorrenza di variabile nelle seguenti formule, dire se si tratta di un’occorrenza libera o vincolata. Per ciascuna formula, elencare le sue variabili libere e dire se si tratta di un enunciato oppure no.
\(((\forall z(P(z,z))) \wedge (\exists x (\forall y ((P(x,y)) \to (P(z,y))))))\)
\((\exists x ((\exists y (f(x) = y)) \vee ((f(y) = x) \leftrightarrow (P(x,y)))))\)
\(((P(c,c)) \wedge (Q(a)))\)
\((\forall z (\exists y ((P(y,x)) \vee (P(c,f(x))))))\)
\(((P(z,x)) \to (\exists x (\forall y (P(z,x)))))\)
Parentesi e priorità
Per facilitare la lettura di una formula è possibile omettere alcune parentesi non necessarie utilizzando opportune convenzioni.
La parentesi più esterne e le parentesi che racchiudono le formule atomiche si omettono sempre.
La gerarchia di priorità dei connettivi vista in logica proposizionale viene aggiornata attribuendo ai quantificatori la stessa priorità della negazione (ovvero priorità massima):
\(\neg\) \(\exists\) \(\forall\)
\(\wedge\) \(\vee\)
\(\rightarrow\)
\(\leftrightarrow\)
Ad esempio, \(\forall z P(z) \to Q(z)\) è equivalente a \((\forall z P(z)) \to Q(z)\) e NON a \(\forall z (P(z) \to Q(z))\) (in quest’ultimo caso non si possono omettere le parentesi, altrimenti la formula cambia di significato).
Per le costanti logiche di massima priorità (ovvero quelle che si applicano ad una formula sola), l’ordine di applicazione è “da destra a sinistra” — questo è l’unica scelta possibile per ottenere una formula reintroducendo le parentesi. Ad esempio, \(\neg \exists x \forall y \, R(x,y)\) è la formula \(\neg(\exists x ( \forall y R(x,y)))\), mentre \(\exists z \neg Q(z)\) è la formula \(\exists z (\neg Q(z))\).
Per connettivi binari dello stesso tipo si usa l’associatività a destra. Ad esempio, se \(\Box\) è un connettivo binario scriveremo \(\phi_{1} \mathrel{\Box} \dotsc \mathrel{\Box} \phi_{n}\) al posto di \(\phi_{1} \mathrel{\Box} \left ( \phi_{2} \mathrel{\Box} (\dotsc \mathrel{\Box}\phi_{n} ) \dotsc \right )\).
Attenzione! Come osservato in alcuni degli esempi precedenti, non tutte le parentesi si possono eliminare da una formula (senza alterarne il significato).
Si possono eliminare parentesi fin tanto che il significato dell’espressione risultante resta univocamente determinato ed identico a quello della formula originale (ovvero alla versione formale con tutte le parentesi). Questo vuol dire che, utilizzando le convenzioni date, si devono poter reintrodurre le parentesi senza ambiguità, fino a ricostruire la formula originale.
Reintrodurre le parentesi nelle seguenti formule, dove \(P\) è un simbolo di relazione unario, \(R\) è un simbolo di relazione binario, \(f\) è un sibolo di funzione binario, \(g\) è un simbolo di funzione unario e \(a,b,c\) sono simboli di costante.
\(\exists x P(x) \to \forall z R(z,y) \wedge g(x) = f(x,y)\)
\(P(x) \wedge \forall z \forall y R(g(z),f(z,y)) \leftrightarrow \neg \forall w (P(w) \wedge P(c))\)
\(\forall x \exists y R(x,x) \to \forall z f(z) = a\)
\(\forall x (\exists y R(x,x) \to \forall z f(z) = a)\)
\(\forall x \exists y ( R(x,x) \to \forall z f(z) = a)\)
\(\neg P(x) \wedge \forall y R(y,z)\)
\(\neg (P(x) \wedge \forall y R(y,z))\)
Il seguente criterio permette di individuare la costante logica principale di una formula da cui siano state omesse alcune parentesi seguendo le convenzioni stabilite.
La costante logica principale di una formula è sempre quella di priorità più bassa tra quelle non contenute in alcuna coppia di parentesi; se ve n’è più di una con queste caratteristiche, la costante logica principale è quella più a sinistra tra di esse.
Nelle seguenti formule (in cui sono state omesse alcune parentesi), la costante logica principale è quella indicata a fianco:
\(\exists x (\forall y R(x,y) \wedge \neg(x=y)) \vee \forall z \neg P(z)\): costante logica principale: OR
\(\neg \exists x (P(x) \rightarrow R(x,x))\): costante logica principale: NOT
\(\forall z P(z) \wedge \neg R(z,z) \wedge \exists z \neg P(z)\): costante logica principale: primo AND
\(\forall x \neg (\exists y R(x,y) \to P(x))\): costante logica principale: FOR ALL
Avendo un modo per individuare il connettivo principale anche in assenza di (alcune) parentesi, possiamo costruire l’albero sintattico senza dover prima reintrodurre tutte le parentesi mancanti.
L’albero sintattico di \(\exists x (\forall y R(x,y) \wedge \neg(x=y)) \vee \forall z \neg P(z)\) è il seguente:
Di ciascuna delle formule seguenti (in cui sono state omesse alcune parentesi), determinare l’albero sintattico e l’altezza.
\(\exists x P(x) \to \forall z (f(z) = x \vee \neg R(x,z))\)
\(\forall w \exists y (P(x) \wedge R(x,z) \leftrightarrow \exists z \neg \forall v R(z,v))\)
\(\neg\exists x (R(x,x) \vee \forall y P(c) \to R(c,c) \wedge P(x))\)
\(\exists x \forall z R(x,z) \to \forall z \exists x R(x,z)\)
\(P(c) \wedge \forall x (P(x) \to P(f(x))) \to \forall x P(x)\)
Di ogni occorrenza di variabile nelle formule precedenti, dire se si tratta di occorrenza libera o vincolata. Elencare le variabili libere di ciascuna formula e dire se si tratta di un enunciato oppure no.